package top.datacluster.basic.algorithm.leetcode.tree;

import top.datacluster.basic.algorithm.leetcode.TreeNode;

public class LeetCode1544 {

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int index = 0;
        TreeNode root = new TreeNode(preorder[index]);
        while (inorder[index] != root.val){
            index++;
        }
        int pos = 1;
        if (index == 0){
            root.left = null;
        }else{
            int[] leftInorder = new int[index];
            for (int i = 0;i < leftInorder.length; i++){
                leftInorder[i] = inorder[i];
            }
            int[] leftPreorder = new int[index];

            for (int i = 0;i < leftPreorder.length; i++){
                leftPreorder[i] = preorder[pos];
                pos++;
            }
            root.left = buildTree(leftPreorder, leftInorder);
        }
        if (index == inorder.length - 1){
            root.right = null;
        }else{
            int[] rightInorder = new int[inorder.length - index - 1];

            for (int i = 0;i < rightInorder.length; i++){
                rightInorder[i] = inorder[i + index + 1];
            }

            int[] rightPreorder = new int[inorder.length - index - 1];
            for (int i = 0;i < rightPreorder.length; i++){
                rightPreorder[i] = preorder[pos];
                pos++;
            }
            root.right = buildTree(rightPreorder, rightInorder);
        }



        return root;
    }

    public static void main(String[] args) {
        int[] left = new int[]{3,9,20,15,7};
        int[] right = new int[]{9,3,15,20,7};
        TreeNode node = new LeetCode1544().buildTree(left, right);
        System.out.println(node.val);
    }
}
